/**
 * @Author: XJH
 * @Description: TODO
 * @Date: 2025/10/22 21:21
 * @Version: 1.0
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: XJH
 * @Description: TODO
 * @Date: 2025/10/22 21:21
 * @Version: 1.0
 */
public class Sum_of_three_numbers {
    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // 排序后，如果第一个数a > 0，那么a + b + c一定 > 0（因为b和c在a右边，都 ≥ a）
            if (nums[i] > 0) {
                break;
            }
            // 去重：如果当前a和前一个a相同，跳过（避免重复三元组）
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            int target = -nums[i]; //因为a+b=-c;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {  // 找到符合条件的三元组
                    // 将[a, b, c]加入结果集
                    //快速创建一个包含指定元素的 List 集合。
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 去重：跳过重复的b（左指针）
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;  // 相同则右移，直到不同
                    }
                    // 去重：跳过重复的c（右指针）
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;  // 相同则左移，直到不同
                    }
                    // 移动指针继续寻找下一组可能的b和c
                    //为什么同时移动，因为移动一个的话 很可能新相加的值 大于小于等于target 我们不需要重复的元组，
                    left++;
                    right--;
                } else if (sum < target) {  // b + c < 目标，需要增大和
                    left++;  // 左指针右移（数组递增，nums[left]变大，sum增大）
                } else {  // sum > target，需要减小和
                    right--;  // 右指针左移（nums[right]变小，sum减小）
                }
            }


        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> result = new Sum_of_three_numbers().threeSum(nums);
        for (List<Integer> triplet : result) {
            System.out.print(triplet);
        }
    }
}
